public class Leetcode {
}

//leetcode:300:最长递增子序列
class Solution1 {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        //创建一个dp表，判断以i位置为结尾的最长子序列长度
        int[] dp = new int[n];
        //单个字符也为子序列列所以我们可以将每个位置的值初始化为1
        for(int i = 0; i < n; i++){
            dp[i] = 1;
        }

        int ret = 0;
        //遍历每个字符
        for(int i = 0; i < n; i++){
            //找这个字符前面的所有字符
            for(int j = 0; j < i; j++){
                //如果值是小于i位置的值的就说明可以递增
                if(nums[j] < nums[i]){
                    //同时得到j位置值的最长递增子序列，让他加一得到新的i位置的子序列长度
                    //判断此时这个j位置的元素与i形成的子序列长度和原本的那个更长
                    //然后更新dp,之后在循环判断
                    dp[i] = Math.max(dp[i] , dp[j]+1);
                }
            }
            //最后判断所有位置的最长子序列那个是最长的
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
}

//leetcode:376:摆动序列
class Solution2 {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        //设立两表，f代表以i位置为结尾的差值为正数的最长长度，g代表以j位置为结尾的差值为负数的最长长度
        int[] f = new int[n];
        int[] g = new int[n];

        //由于单个元素也为摆动序列，那么我们可以将所有位置的值初始为1
        for(int i = 0; i < n; i++){
            f[i] = g[i] = 1;
        }

        int ret = 0;
        //遍历每个位置
        for(int i = 0; i < n; i++){
            //找这个位置前面的所有元素
            for(int j = 0; j < i; j++){
                //如果元素小于i位置的值，那么差值就为正数，此时长度就为j位置差值为负数的值加一与i位置差值为正数的长度的最大值
                if(nums[j] < nums[i]) f[i] = Math.max(f[i] , g[j] + 1);
                //如果元素大于i位置的值，那么差值就为负数，此时长度就为j位置差值为正数的值加一与i位置差值为负数的长度的最大值
                if(nums[j] > nums[i]) g[i] = Math.max(g[i] , f[j] + 1);
            }
            //得到每个位置差值为正和负这两种情况的最大长度
            //然后得到每个位置最大长度中的最大值
            ret = Math.max(ret,Math.max(f[i] , g[i]));
        }
        return ret;
    }
}